COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002			On LISP and Semantics of Programming Languages
C00012 ENDMK
C⊗;
		On LISP and Semantics of Programming Languages

	LISP should be the first language learned by Computer Science majors.
As a mathematical language for studies algorithms for data structures, it is
presently without peer.  As you are seeing now, the problems of language implementation and their solutions are describable
quite easily in the implementation of LISP (symbol tables, hashing, garbage
collection, stacks, linked allocation, lists, etc. etc.)  At the theoretical
level, questions of provability of properties of programs are tractable.  As a
programming language, LISP has exceptionally powerful features possessed by few
languages.  In particular the uniform representation of program and data.  LISP
is also of interest in the study of the semantics of programming languages.  The
study of semantics is motivated by the desire to have a tool for describing
the meaning of constructs of a language.  In particular, a tool of the power and
clarity of BN descriptions of the syntax of languages.

	There are many different schools of thought concerning appropriate means
for describing semantics.  I will describe a few in my usual objective style.
One thought is to describe the meaning of a language in terms of the process
of compilation.  That is, the semantic is specified by some canonical compiler
producing code of some standard machine-independent machine.  The meaning of
a program is the outcome of an interpreter interpreting this machine-independent
code.

	The key problem is:  just what is the semantic specification supposed to
do?  If it is truly to help a programmer (be he implementor or applications)
to understand the meaning of a particular constructs, then this proposal is
lacking.  To understand a construct now requires that you read the description 
of a compiler--a non-trivial task, and understand two machines-- the machine-
independent and the real machine.  There is a more fundamental difficulty here.
When you look at a statement of a high-level language you think about the effect
the statement will have on the environment of your program when it executes, you
do not think about the code that gets generated and then think about the

execution of that code.  Thus modeling semantics in terms of a compiler model is
additing one level of obfuscation.  A more natural description of the meaning of
constructs is given in terms of the run-time behavior of these constructs.
That's what LISP does.  The eval function describes the execution sequence of a
representation of an arbitrary LISP expression.  Thus eval is the semantic
description of LISP.  Now certain timid souls shrink from this resulting
circularity:  the description of the semantics of a language in that language.
Circularity is inevitable, lie back and enjoy it.

	Attempts have been made to give non-circular interpreter-based
descriptions of semantics for languages other than LISP.  There is the
incredible VDL description of PL/1; and the convoluted description of ALGOL 68
by a Markov algorithm.

	To describe meaning in terms of 'self-evident' string manipulations
is misplaced rigor.  If a semantic description is to be anything more than a
sterile game it must be useful to implementors as well as applications
programmers.  If you decide to describe the semantics of language L1 in a
simpler language L2 then either L2 is 'self evident' or you must give a
description of the meaning of L2, etc.  So either you go circular or you end
up with a (useless) 'self-evident' Ln.

	There are very good reasons for deciding on direct circularity.  First,
you need only learn one language.  If the semantic specification is given
the source language, then you learn the programming language and the
semantic (meta) language at the same time.  Second, since the evaluator is
written in the language, we can understand the language by understanding
the workings of the single program, eval; and if we wish to modify the
semantics we need change only one (source language) program.  Thus, if we
wished to add new language constructs to LISP (like the prog feature) we
need only modify eval so that it recognizes an occurrence of a (sexpr
representation of a) prog, add a new (semantic) function to describe the
interpretation of the construct and we're done.


			More on Compilation


	As we have described in previous notes the processes of evaluation
and compilation are parallel:  the evaluator performs the evaluation; the
compiler emits instructions which when executed produce the same computational
effect as the evaluator.  We can exploit this parallelism when we write the
LISP function, compile, which will describe the compiler.  The input to
compile is the sexpr representation of a LISP function; the output is a list
which represents a sequence of machine instructions.  Assume that we have
LISP running on Brand X machine, and we have just written the LISP function,
compile, which produces code for Brand X machine. Then:

	1.  Write the Sexpression form of compile.

	2.  Read in this translation using define.

	3.  Ask LISP to evaluate:  compile[COMPILE].

Now since compile is a function of one argument which proports to compile code
for Brand X machine, translating the sexpression representation of its argument
to machine code, the output of step 3. should be a list of instructions 
representing the translation of the function compile.  That is, step 3. compiles
the compiler!!

	Obviously, before we can use this compiled version of the compiler (or
in fact, before we can use any compiled code) we must have some means of
translating the list output of the compile function into real instructions in the
machine.  So if the version of LISP which we are implementing is to have a
compiler we must allocate an area of memory which can receive the compiled code.
This area is usually called Binary Program Space (BPS).  The translation program
which takes the list of output from the compiler and converts it onto actual
machine instructions for BPS is called an assembler.

				One-pass Assemblers


	An example:  The output from compile for the function:

		j[x;y] = f[g[x];h[y]]

would be the list:

(LAP SUBR   J)			; says `j' is a function

(PUSH P AC1)			; save the input args